Benchmarks
Comparaison de fonctions avec Criterion
Comparatif HsIndex
Comparatif sort . nub vs nub . sort
Comparatif sort . nub vs nub . sort (Suite)
Comparatif de performance de fonctions de filtrage de mots
Comparatif de performance de fonctions de filtrage de mots (Suite)
Comparatif de performance de fonctions pour calculer la distance de Levenshtein avec un seuil
Comparatif de performance de fonctions de filtrage de mots
Introduction
Pour un de mes programmes, je suis amené à filtrer et supprimer certains mots d'un texte long. J'ai besoin de supprimer les pronoms, les verbes conjugués, les déterminants et certains autres mots.
La première façon de faire serait de simplement filtrer la liste de mots wrdstxt en testant l'absence de chaque mot de la liste wrdsfilt en utilisant notElem:
filterByList (wrdsfilt, wrdstxt) = filter (`notElem` wrdsfilt) wrdstxt
Pour un petit nombre de mots servant de filtre, cette fonction serait adaptée, mais plus le nombre de mots à supprimer va augmenter, plus le temps de traitement va augmenter 1.
Il faut donc trouver un moyen d'optimiser le processus.
La solution serait de stocker les mots non plus dans une liste mais dans un arbre de recherche. Les mots ainsi triés et organisés seraient plus rapides à rechercher.
Après avoir recherché de la documentation sur le sujet, j'ai trouvé plusieurs solutions permettant de répondre à mon problème.
Mais quelle est la solution la plus performante ?
C'est ce que nous allons voir dans ce benchmark!
Méthodologie
Matériel
Ce test sera réalisé sur une machine tournant sous Linux Debian 10 avec un processeur AMD Ryzen 7 3700X 8 cœurs 16 threads avec 32Go de mémoire DDR4.
Généralité
Le benchmark sera réalisé avec Haskell et Criterion avec toutes les optimisations de compilation activées ghc -o2 -fforce-recomp.
La liste de mots à filtrer sera celle-ci: Mots_a_filtrer.txt
Le texte à balayer sera Voyage au centre de la terre récupéré sur le site Gutenberg
Les mots seront chargés avant le test, afin de ne pas fausser les résultats.
Les arbres de recherches seront créés pendant le test afin de prendre en compte le temps de création de l'arbre.
Solutions
Les différentes solutions passées en revue sont :
Data.Set
Le paquet container fournit différents modules standards pour stocker des données et notamment les Set.
Cette structure est un arbre de recherche binaire (2 branches) automatiquement équilibré lors de sa création.
Arbre personnalisé multibranche (WordTree1)
Cet arbre est un arbre de ma propre conception contenant une branche pour chaque lettre de l'alphabet. L'ordre des arbres, correspond à l'ordre alphabétique: abcdefghijklmnopqrstuvwxyz
Cet arbre ne peut pas se rééquilibrer tout seul.
La fonction member permettant de tester la présence d'un élément est implémenté de cette manière:
member v0 tree = go v0 tree
where
go _ Tip = False
go _ t@(Fork vs Tip Tip Tip Tip Tip Tip Tip Tip Tip Tip Tip Tip Tip Tip Tip Tip Tip Tip Tip Tip Tip Tip Tip Tip Tip Tip) = v0 `elem` vs
go [] t@(Fork vs _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ ) = v0 `elem` vs
go (a : as) (Fork vs t1 t2 t3 t4 t5 t6 t7 t8 t9 t10 t11 t12 t13 t14 t15 t16 t17 t18 t19 t20 t21 t22 t23 t24 t25 t26) | a == 'a' = go as t1
| a == 'b' = go as t2
| a == 'c' = go as t3
| a == 'd' = go as t4
| a == 'e' = go as t5
| a == 'f' = go as t6
| a == 'g' = go as t7
| a == 'h' = go as t8
| a == 'i' = go as t9
| a == 'j' = go as t10
| a == 'k' = go as t11
| a == 'l' = go as t12
| a == 'm' = go as t13
| a == 'n' = go as t14
| a == 'o' = go as t15
| a == 'p' = go as t16
| a == 'q' = go as t17
| a == 'r' = go as t18
| a == 's' = go as t19
| a == 't' = go as t20
| a == 'u' = go as t21
| a == 'v' = go as t22
| a == 'w' = go as t23
| a == 'x' = go as t24
| a == 'y' = go as t25
| otherwise = go as t26
go _ _ = False
Le module complet se trouve ici : WordTree1.hs
Arbre personnalisé multibranche (WordTree2)
Cet arbre est du même type que l'arbre WordTree1 a ceci près que l'ordre des arbres correspond à l'ordre des lettres les plus couramment utilisées dans la langue française2: eairsntolucmpdghbfvyqkzx
member v0 tree = go v0 tree
where
go _ Tip = False
go _ t@(Fork vs Tip Tip Tip Tip Tip Tip Tip Tip Tip Tip Tip Tip Tip Tip Tip Tip Tip Tip Tip Tip Tip Tip Tip Tip Tip) = v0 `elem` vs
go [] t@(Fork vs _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ ) = v0 `elem` vs
go (a : as) (Fork vs t1 t2 t3 t4 t5 t6 t7 t8 t9 t10 t11 t12 t13 t14 t15 t16 t17 t18 t19 t20 t21 t22 t23 t24 t25) | a == 'e' = go as t1
| a == 'a' = go as t2
| a == 'i' = go as t3
| a == 'r' = go as t4
| a == 's' = go as t5
| a == 'n' = go as t6
| a == 't' = go as t7
| a == 'o' = go as t8
| a == 'l' = go as t9
| a == 'u' = go as t10
| a == 'c' = go as t11
| a == 'm' = go as t12
| a == 'p' = go as t13
| a == 'd' = go as t14
| a == 'g' = go as t15
| a == 'h' = go as t16
| a == 'b' = go as t17
| a == 'f' = go as t18
| a == 'v' = go as t19
| a == 'y' = go as t20
| a == 'q' = go as t21
| a == 'k' = go as t22
| a == 'z' = go as t23
| a == 'x' = go as t24
| otherwise = go as t25
go _ _ = False
Le module complet se trouve ici : WordTree2.hs
Cet arbre ne peut pas se rééquilibrer tout seul.
Arbre personnalisé multibranche groupées (WordTree2g)
Cet arbre est une modification de l'arbre WordTree2 avec un regroupement de certaines lettres dans certaines branches de l'arbre. Ce regroupement est effectué en fonction des occurrences de ces lettres et effectué à l'aide de la fonction elem.
Le regroupement des lettres sera:
-
E
-
A
-
I
-
R
-
S
-
N
-
T
-
O
-
LU
-
CMP
-
DGHB
-
…
member v0 tree = go v0 tree
where
go _ Tip = False
go _ t@(Fork vs Tip Tip Tip Tip Tip Tip Tip Tip Tip Tip Tip Tip) = v0 `elem` vs
go [] t@(Fork vs _ _ _ _ _ _ _ _ _ _ _ _ ) = v0 `elem` vs
go (a : as) (Fork vs t1 t2 t3 t4 t5 t6 t7 t8 t9 t10 t11 t12) | a == 'e' = go as t1
| a == 'a' = go as t2
| a == 'i' = go as t3
| a == 'r' = go as t4
| a == 's' = go as t5
| a == 'n' = go as t6
| a == 't' = go as t7
| a == 'o' = go as t8
| elem a "lu" = go as t9
| elem a "cmp" = go as t10
| elem a "dghb" = go as t11
| otherwise = go as t12
go _ _ = False
Le module complet se trouve ici : WordTree2g.hs
Arbre personnalisé multibranche (WordTree3)
Cet arbre est une amélioration de l'arbre WordTree2. L'ordre des arbres correspond à l'ordre des lettres le plus couramment utilisé dans la liste de mots à filtrer3:
member v0 tree = go v0 tree
where
go _ Tip = False
go _ t@(Fork vs Tip Tip Tip Tip Tip Tip Tip Tip Tip Tip Tip Tip Tip Tip Tip Tip Tip Tip Tip Tip Tip Tip Tip Tip) = v0 `elem` vs
go [] t@(Fork vs _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ ) = v0 `elem` vs
go (a : as) (Fork vs t1 t2 t3 t4 t5 t6 t7 t8 t9 t10 t11 t12 t13 t14 t15 t16 t17 t18 t19 t20 t21 t22 t23 t24) | a == 'e' = go as t1
| a == 't' = go as t2
| a == 'u' = go as t3
| a == 's' = go as t4
| a == 'i' = go as t5
| a == 'a' = go as t6
| a == 'o' = go as t7
| a == 'r' = go as t8
| a == 'n' = go as t9
| a == 'l' = go as t10
| a == 'c' = go as t11
| a == 'd' = go as t12
| a == 'q' = go as t13
| a == 'p' = go as t14
| a == 'f' = go as t15
| a == 'v' = go as t16
| a == 'm' = go as t17
| a == 'x' = go as t18
| a == 'z' = go as t19
| a == 'h' = go as t20
| a == 'g' = go as t21
| a == 'j' = go as t22
| a == 'y' = go as t23
| otherwise = go as t24
go _ _ = False
Le module complet se trouve ici : WordTree3.hs
Arbre personnalisé multibranche groupées (WordTree3g)
Cet arbre est une modification de l'arbre WordTree3 avec un regroupement de certaines lettres dans certaines branches de l'arbre. Ce regroupement est effectué en fonction des occurrences de ces lettres et effectué à l'aide de la fonction elem.
Le regroupement des lettres sera:
-
E
-
T
-
U
-
R
-
S
-
IA
-
OR
-
NLC
-
DQPFVMXZH
-
…
member v0 tree = go v0 tree
where
go _ Tip = False
go _ t@(Fork vs Tip Tip Tip Tip Tip Tip Tip Tip Tip) = v0 `elem` vs
go [] t@(Fork vs _ _ _ _ _ _ _ _ _ ) = v0 `elem` vs
go (a : as) (Fork vs t1 t2 t3 t4 t5 t6 t7 t8 t9) | a == 'e' = go as t1
| a == 't' = go as t2
| a == 'u' = go as t3
| a == 's' = go as t4
| elem a "ia" = go as t5
| elem a "or" = go as t6
| elem a "nlc" = go as t7
| elem a "dqpfvmxzh" = go as t8
| otherwise = go as t9
go _ _ = False
Le module complet se trouve ici : WordTree3g.hs
Fonctions de test
Lecture des fichiers texte
Les listes de mots à filtrer et servant de filtres sont lues depuis un fichier texte avec readFile puis découpés en mots, convertit en minuscule avec map (map toLower) . words et renvoyés sous forme d'un doublet.
Cette fonction est exécutée hors test pour ne pas prendre en compte le temps de construction des listes dans le test.
readWordsIO :: FilePath -> FilePath -> IO ([String], [String])
readWordsIO pathfil pathtxt = do
wrdsfil <- map (map toLower) . words <$> readFile pathfil
wrdstxt <- map (map toLower) . words <$> readFile pathtxt
return (wrdsfil, wrdstxt)
Filtrage
Le filtrage des listes se fera avec des fonctions identiques utilisant la fonction member de chaque module.
Seule la fonction de fitlrage par liste est un peu différente, utilisant notElem.
filterByList (wrdsfilt, wrdstxt) = filter (`notElem` wrdsfilt) wrdstxt
filterTextSet (wrdsfilt, wrdstxt) = filter (\w -> not (Set.member w tree)) wrdstxt
where tree = Set.fromList wrdsfilt
filterText1 (wrdsfilt, wrdstxt) = filter (\w -> not (WT1.member w tree)) wrdstxt
where tree = WT1.fromList wrdsfilt
Construction
La construction des arbres sera évaluée simplement avec la fonction fromList de chaque module.
constSet (wrdsfilt, wrdstxt) = Set.fromList wrdsfilt
constTree1 (wrdsfilt, wrdstxt) = WT1.fromList wrdsfilt
Résultats
Temps de filtrage
Les valeurs données par le benchmark sont les suivantes:
|
Lists |
Set |
WordTree 1 |
WordTree 2 |
WordTree 2g |
WordTree 3 |
WordTree 3g |
|
|---|---|---|---|---|---|---|---|
|
sec |
96,44437 |
8,73092 |
7,63710 |
6,94024 |
10,84359 |
6,83521 |
15,85130 |
|
xfaster/List |
/ |
11,0463 |
12,6284 |
13,8964 |
8,8941 |
14,1099 |
6,0843 |
|
%lower/List |
/ |
-90,95 % |
-92,08 % |
-92,80 % |
-88,76 % |
-92,91 % |
-83,56% |
|
xfaster/Set |
/ |
/ |
1,14 |
1,26 |
0,81 |
1,28 |
0,55 |
|
%lower/Set |
/ |
/ |
-12,53 % |
-20,51 % |
24,20 % |
-21,71 % |
81,55 % |
![!!! File report-Voyage-full1_p1.[1131x1600@256d].png not found !!!](report-Voyage-full1_p1.[1131x1600@256d].png)
![!!! File report-global1_p1.[1131x1600@256d].png not found !!!](report-global1_p1.[1131x1600@256d].png)
On remarque déjà l'écart entre le filtrage par liste et le filtrage avec des arbres. Le gain est énorme ! Le traitement est 10 fois plus rapide qu'avec la liste.
On remarque également que si le le filtrage avec le Set est très performant, un filtrage avec un arbre dédié a chaque lettre est un peu plus rapide.
On voit déjà que l'idée de regrouper les lettres dans certaines branches avec la fonction elem est une mauvaise idée. Ces fonctions bien que plus rapide que le tri par liste sont plus lentes que le tri par Set et surtout plus lentes que leur version non groupée.
On constate aussi que l'arbre WordTree2 est un peu plus rapide que l'arbre WordTree1 et que l'arbre WordTree3 est un peu plus rapide que le WordTree2.
Il est donc intéressant d'avoir un arbre dont le classement est optimisé pour la liste de mots servant de filtre.
Temps de construction des arbres
Comme on le voit sur ce tableau récapitulatif, Le temps de construction d'un set est beaucoup plus important que l'arbre WordTree1 (environ 5 fois plus lent). Cela s'explique très bien car les Set sont des arbres qui s'équilibrent automatiquement lors de leur construction. Cela nécessite des tests et des modifications de l'arbre qui entraîne un ralentissement de la construction.
On remarque également que plus on utilise un arbre adapté (optimisé) pour les mots servant de filtre, plus son temps de construction est faible.
|
Set |
WordTree 1 |
WordTree 2 |
WordTree 2g |
WordTree 3 |
WordTree 3g |
|
|---|---|---|---|---|---|---|
|
sec |
0,04696 |
0,00831 |
0,00781 |
0,01192 |
0,00784 |
0,01606 |
|
xfaster/Set |
1,00 |
5,65 |
6,02 |
3,94 |
5,99 |
2,92 |
|
%lower/Set |
/ |
-82,30 % |
-83,38 % |
-74,62 % |
-83,31 % |
-65,80 % |
![!!! File report-construct-full1_p1.[1131x1600@256d].png not found !!!](report-construct-full1_p1.[1131x1600@256d].png)
Conclusion
Utiliser un filtrage par arbre est extrêmement intéressant est permet d'accélérer considérablement le traitement par rapport à un filtrage par liste. Le gain étant de l'ordre de 90%
Un arbre adapté aux mots servant de filtre permet également d'accélérer le traitement. Le gain pouvant aller jusqu'a 20%/25% par rapport à un Set.
Néanmoins, réaliser une statistique des lettres utilisées et implémenter un arbre optimisé pour cette série prend du temps.
Pour un usage occasionnel et standard, l'utilisation d'un Set reste la solution la plus simple et la plus rapide à mettre en œuvre.
Pour un usage intensif sur une quantité massive de données, utiliser un arbre dédié peut accélérer notablement le temps de traitement.
Notes
|
1.↑ |
Le temps de traitement augmentera de façon exponentielle. |
|
2.↑ |
Lettres les plus utilisées dans la langue française Selon cette page, les lettres les plus souvent utilisées dans la langue française sont:
|
|
3.↑ |
Une analyse faite a part a montrée que les lettres les plus courantes dans les mots à chercher sont: \ [('e',133),('s',103),('u',102),('t',90),('i',85),('a',77),('o',61),('n',59),('r',49),('l',46),('c',34),('d',27),('q',21),('p',21),('v',21),('f',19),('m',18),('x',9),('g',9),('z',8),('j',5),('y',4),('h',4),('b',4)] \ [('a',77),('b',4),('c',34),('d',27),('e',133),('f',19),('g',9),('h',4),('i',85),('j',5),('l',46),('m',18),('n',59),('o',61),('p',21),('q',21),('r',49),('s',103),('t',90),('u',102),('v',21),('x',9),('y',4),('z',8)]
|